{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #训练计划 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trainningPlan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #训练计划 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个头节点为 <code>head</code> 的单链表用于记录一系列核心肌群训练编号，请将该系列训练编号 <strong>倒序</strong> 记录于链表并返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5]\n",
    "<strong>输出：</strong>[5,4,3,2,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2]\n",
    "<strong>输出：</strong>[2,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目范围是 <code>[0, 5000]</code></li>\n",
    "\t<li><code>-5000 &lt;= Node.val &lt;= 5000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意</strong>：本题与主站 206 题相同：<a href=\"https://leetcode-cn.com/problems/reverse-linked-list/\">https://leetcode-cn.com/problems/reverse-linked-list/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fan-zhuan-lian-biao-lcof](https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fan-zhuan-lian-biao-lcof](https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[1,2]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 正向遍历链表，不断缓存下一个节点，修改当前节点指向\n",
    "        pre, cur = None, head\n",
    "\n",
    "        while cur is not None:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head==None:\n",
    "            return head\n",
    "        p=None\n",
    "        q=head\n",
    "        k=head.next\n",
    "        while k:\n",
    "            q.next=p;\n",
    "            p=q;\n",
    "            q=k;\n",
    "            k=k.next;\n",
    "        q.next=p\n",
    "        return q;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur,pre = head,None\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur,pre = head, None\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next=pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        return pre\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre=None\n",
    "        cur=head\n",
    "        while cur:\n",
    "            nxt=cur.next\n",
    "            cur.next=pre\n",
    "            pre=cur\n",
    "            cur=nxt\n",
    "        return pre\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l = ListNode()\n",
    "        l.next = None\n",
    "        while head!=None:\n",
    "            p = head.next\n",
    "            head.next = l.next\n",
    "            l.next = head\n",
    "            head=p\n",
    "        return l.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        pre = None\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            next = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = next\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return None\n",
    "        else:\n",
    "            last = ListNode(head.val)\n",
    "            head = head.next\n",
    "        while head:\n",
    "            c = ListNode(head.val)\n",
    "            c.next = last\n",
    "            last = c\n",
    "            head = head.next\n",
    "        \n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        values = []\n",
    "        while head:\n",
    "            values.append(head.val)\n",
    "            head = head.next\n",
    "        \n",
    "        for i, val in enumerate(values[::-1]):\n",
    "            cur = ListNode(val, None)\n",
    "\n",
    "            if i == 0:\n",
    "                head = cur\n",
    "            else:\n",
    "                prev.next = cur\n",
    "\n",
    "            prev = cur\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# class Solution:\n",
    "#     def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "#         pre = None\n",
    "#         cur = head\n",
    "#         while cur:\n",
    "#             tmp = cur.next\n",
    "#             cur.next = pre\n",
    "#             pre = cur\n",
    "#             cur = tmp\n",
    "#         return pre\n",
    "\n",
    "# class Solution:\n",
    "#     def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # if not head:\n",
    "        #     return None\n",
    "        # l = []\n",
    "        # while head:\n",
    "        #     l.append(head.val)\n",
    "        #     head = head.next\n",
    "        # l = l[::-1]\n",
    "        # tempHead = ListNode(l[0])\n",
    "        # root = tempHead\n",
    "        # for i in range(1,len(l)):\n",
    "        #     temp = ListNode(l[i])\n",
    "        #     root.next = temp\n",
    "        #     root = temp\n",
    "        # return temp\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        l = []\n",
    "        while head:\n",
    "            l.append(head.val)\n",
    "            head = head.next\n",
    "        l.reverse()\n",
    "        tempHead = ListNode(l[0])\n",
    "        root = tempHead\n",
    "        for i in range(1,len(l)):\n",
    "            temp = ListNode(l[i])\n",
    "            root.next = temp\n",
    "            root = temp\n",
    "        return tempHead\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pass\n",
    "        # 特殊值检查\n",
    "        if head is None:\n",
    "            return None\n",
    "\n",
    "        # 正向遍历input链表，不断创建新head节点指向pre节点\n",
    "        new_head = ListNode(val=head.val, next=None)\n",
    "        while head.next is not None:\n",
    "            head = head.next\n",
    "            new_head = ListNode(val=head.val, next=new_head)\n",
    "\n",
    "        return new_head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans=[]\n",
    "        while (head is not None):\n",
    "            ans.append(head.val)\n",
    "            head=head.next\n",
    "        new_list=ListNode()\n",
    "        head_new=new_list\n",
    "        for i in range(1,len(ans)+1):\n",
    "            node=ListNode(ans[-i])\n",
    "            head_new.next=node\n",
    "            head_new=node\n",
    "        return new_list.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # ==================== 逆转链表 ====================\n",
    "        # 方法一：堆栈方法\n",
    "        temp = []\n",
    "        while head:\n",
    "            temp.append(head.val)\n",
    "            head = head.next\n",
    "        head = ListNode(0)\n",
    "        cur = head\n",
    "        for val in temp[::-1]:\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "        return head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head and head.next:\n",
    "            last = ListNode(head.val)\n",
    "        else:\n",
    "            return head\n",
    "        while head.next:\n",
    "            last_second = ListNode(head.next.val, last)\n",
    "            last = last_second\n",
    "            head = head.next\n",
    "        return last_second\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None: return None\n",
    "        if head.next is None: return head\n",
    "        p=head\n",
    "        tmp=[]\n",
    "        while(p):\n",
    "            tmp.append(p.val)\n",
    "            p=p.next\n",
    "        new=ListNode(-1)\n",
    "        p=new\n",
    "        for va in tmp[::-1]:\n",
    "            p.next=ListNode(va)\n",
    "            p=p.next\n",
    "        return new.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        nums = []\n",
    "\n",
    "        while head:\n",
    "            nums = [head.val] + nums\n",
    "            head = head.next\n",
    "\n",
    "        ans = ListNode(nums[0])\n",
    "        \n",
    "        nums = nums[1:]\n",
    "        temp = ans\n",
    "        while nums:\n",
    "            n = ListNode(nums[0])\n",
    "            temp.next = n\n",
    "            temp = temp.next\n",
    "            \n",
    "            nums = nums[1:]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        last = self.trainningPlan(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        res=[]\n",
    "        if head==None:\n",
    "            return head\n",
    "        def Reverse(head,res):\n",
    "            if head==None:\n",
    "                return\n",
    "            Reverse(head.next,res)\n",
    "            res.append(head.val)           \n",
    "        Reverse(head,res)\n",
    "        thead=ListNode(res[0])\n",
    "        temphead=thead\n",
    "        for i in range(1,len(res)):\n",
    "            temp=ListNode(res[i])\n",
    "            temphead.next=temp\n",
    "            temphead=temp\n",
    "        return thead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def recur(cur, pre):\n",
    "            if not cur: return pre\n",
    "            res = recur(cur.next, cur)\n",
    "            cur.next = pre\n",
    "            return res\n",
    "\n",
    "        return recur(head, None)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # pre, cur = None, head\n",
    "        # while cur:\n",
    "        #   tem = cur.next\n",
    "        #    cur.next = pre\n",
    "        #    pre = cur\n",
    "        #    cur = tem\n",
    "        # return pre\n",
    "        \n",
    "        def re(pre, cur):\n",
    "            if not cur: return pre\n",
    "            res = re(cur, cur.next)\n",
    "            cur.next = pre\n",
    "            return res\n",
    "        return re(None,head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # cur,pre = head,None\n",
    "        # while cur:\n",
    "        #     tmp = cur.next\n",
    "        #     cur.next = pre\n",
    "        #     pre = cur\n",
    "        #     cur = tmp\n",
    "        # return pre\n",
    "\n",
    "        def recur(cur,pre):\n",
    "            if not cur:\n",
    "                return pre\n",
    "            res = recur(cur.next,cur)\n",
    "            cur.next = pre\n",
    "            return res\n",
    "        return recur(head,None)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]: \n",
    "        def recur(cur,pre):\n",
    "            if not cur :return pre\n",
    "            res=recur(cur.next,cur)\n",
    "            cur.next=pre\n",
    "            return res\n",
    "        return recur(head,None)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
